import math
from decimal import *
from copy import deepcopy
from algorithm.classify.module import Module
from common import datasetInfo

class C45():
    def __init__(self, table_name, table, class_label_attribute, accuracy):
        self.table = table
        self.table_name = table_name
        self.record_num = len(self.table)
        self.class_label_attribute = class_label_attribute
        self.accuracy = float(accuracy)
        self.result = []
        self.attribute_num = {}
        self.attributes = getattr(datasetInfo, 'attribute_list')[self.table_name]

        i = 0
        self.attribute_list = []
        for item in self.attributes.split(", "):
            self.attribute_list.append(item) 
            self.attribute_num[item] = i
            i = i + 1

    def ignoreAttribute(self, ignore_list):
        self.attribute_list.remove(self.class_label_attribute)
        for attr in ignore_list:
            self.attribute_list.remove(attr)
        return True

    def size(self, set):
        return len(set)

    def p(self, subset, set):
        getcontext().prec = 6
        return float(Decimal(self.size(subset)) \
               / Decimal(self.size(set)))

    def getValue(self, tupe, attribute):
        return tupe[self.attribute_num[attribute]]

    def getSubsetList(self, mainset, attribute):
    #split the mainset according to the value of attribute
        subset_list = {}
        for tupe in mainset:
            subset_key = self.getValue(tupe, attribute)
            if subset_key not in subset_list:
                 subset_list[subset_key] = []
            subset_list[subset_key].append(tupe)
        return subset_list

    def I(self, mainset):
        subset_list = self.getSubsetList(mainset, self.class_label_attribute)
        
        result = 0
        for element in subset_list:
            pi = self.p(subset_list[element], mainset)
            result = result + pi * math.log(pi, 2)
        return result * -1
     
    def GainRate(self, mainset, test_attri):
        subset_list = self.getSubsetList(mainset, test_attri)
        
        E = 0
        for element in subset_list:
            E = E \
                + self.p(subset_list[element], mainset) \
                * self.I(subset_list[element])

        I_total = self.I(mainset)
        Gain = I_total - E
        result = Gain / I_total
        return result
    
    def isLeaf(self, leaf_info):
        for item in leaf_info["accuracy_list"]:
            if item["acc"] > self.accuracy:
                leaf_info["class_res"] = item["cla"]
                leaf_info["position"] = "leaf"
                leaf_info["next_decision_attribute"] = "none"
        return leaf_info

    def updateAccuracyList(self, node, set_remain, subset_list):
        del node["accuracy_list"][:]
        node["branch_size"] = len(set_remain)
        for subset in subset_list:
            cur_accuracy = self.p(subset_list[subset], set_remain)
            node["accuracy_list"].append({"cla":subset, "acc":cur_accuracy})
        return node

    def makeTree(self, set_remain, attribute_remain, branch_info):
        node_info = deepcopy(branch_info)
        subset_list = self.getSubsetList(set_remain, self.class_label_attribute)
        self.updateAccuracyList(node_info, set_remain, subset_list)
        self.isLeaf(node_info)
        
        if node_info["position"] == "leaf":
            return node_info

        if len(attribute_remain) == 0:
            node_info["class_res"] = "not a class"
            node_info["position"] = "leaf"
            node_info["next_decision_attribute"] = "none"
            return node_info

        if len(attribute_remain) == 1:
            next_branch_node = attribute_remain[0]
        else:
            max_rate = -1
            for attribute in attribute_remain:
                cur_rate = self.GainRate(set_remain, attribute)
                if cur_rate > max_rate:
                    max_rate = cur_rate
                    next_branch_node = attribute
        node_info["next_decision_attribute"] = next_branch_node
        branch_list = self.getSubsetList(set_remain, next_branch_node)
        next_attribute_remain = list(attribute_remain)
        next_attribute_remain.remove(next_branch_node)
        node_info2 = deepcopy(node_info)
        node_info2["position"] = "branch"
        node_info["children"] = []
        for branch_value in branch_list:
            next_node_info = deepcopy(node_info2)
            next_node_info["branch_attribute"] = next_branch_node
            next_node_info["branch_value"] = branch_value
            next_node_info["branch_list"][next_branch_node] = branch_value
            node_info["children"].append( \
                self.makeTree(branch_list[branch_value], next_attribute_remain, next_node_info))
        return node_info

    def classify(self):
        root_info = {"class_res": "not a class",
                     "position": "root",
                     "next_decision_attribute": "", 
                     "branch_attribute": "",
                     "branch_value": "", 
                     "branch_size": "0",
                     "branch_list": {},
                     "accuracy_list": []}
        self.result.append(self.makeTree(self.table, self.attribute_list, root_info))
        return self.result

    def showInfo(self, node):
        
        print ">>>node information begin"
        print "class:", node["class_res"]
        print "position:", node["position"]
        print "we are from:", node["branch_attribute"], "=", node["branch_value"]
        print "next_decision_attribute:", node["next_decision_attribute"]
        print "branch:"
        for key, value in node["branch_list"].items():
            print "......", key, "=", value
        print "accuracy:"
        for item in node["accuracy_list"]:
            print "...... class =", item["cla"], ":", item["acc"]
        if "children" in node:
            print ">>>children list begin:"
            for child in node["children"]:
                self.show_info(child)
            print ">>>children list end"
        print ">>>node information end"
        
